package leetcode3;
import java.util.*;
public class Day19 {




    public int firstUniqChar(String s) {
        //思路：使用map记录每个字符的次数和位置（数组下标）
        int[] map = new int[26];
        for(int i=0;i<s.length();i++) {
            map[s.charAt(i)-97]++;
        }

        for(int i=0;i<s.length();i++) {
            if(map[s.charAt(i)-97]==1) return i;
        }
        return -1;
    }

    public int widthOfBinaryTree(TreeNode root) {
        //队列存放结点+编号的二元组
        int width = 1;
        Queue<Integer> indexQueue = new LinkedList<>();//记录结点对应下标
        Queue<TreeNode> queue = new LinkedList<>();
        indexQueue.add(1);
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int min=0,max=0;
            for(int i=0;i<size;i++) {
                //1.弹出节点和对应的下标
                TreeNode parent = queue.poll();
                int index = indexQueue.poll();
                //2.记录最左边节点下标和最右边节点下标
                if(i==0) min = index;
                if(i==size-1) max = index;
                //3.存储它们的孩子节点
                if(parent.left!=null) {
                    queue.add(parent.left);
                    indexQueue.add(index*2);
                }
                if(parent.right!=null) {
                    queue.add(parent.right);
                    indexQueue.add(index*2+1);
                }
            }
            //4.记录本层的最大宽度
            width = Math.max(width,max-min+1);
        }
        return width;
    }
}
